// https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/submissions/563096400/
// 二叉树层序遍历2

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> q1, q2;
        q1.push(root);
        vector<vector<int>> ret;
        vector<int> tmp;
        while(!q1.empty() || !q2.empty())
        {
            TreeNode* cur = nullptr;
            if(!q1.empty())
            {
                while(!q1.empty())
                {
                    if((cur = q1.front()) != nullptr)
                    {
                        tmp.push_back(cur->val);
                        q2.push(cur->left);
                        q2.push(cur->right);
                    }
                    q1.pop();
                }
            }
            else
            {
                while(!q2.empty())
                {
                    if((cur = q2.front()) != nullptr)
                    {
                        tmp.push_back(cur->val);
                        q1.push(cur->left);
                        q1.push(cur->right);
                    }
                    q2.pop();
                }
            }
            if(!tmp.empty())
                ret.push_back(tmp);
            tmp.clear();
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

